

; data segment
;     dw  142,999,1212,664,235,246,235,100,783,315,435,123;,1,5,3,4,9;,6;,8,9,10,11,12,13,14,15,16,17
; data ends

; stackmg segment stack
;     stackmg_stack dw 300 dup(0)  ;1 * 1000 
; stackmg ends

; pointers segment
;     pointers_start   dw 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30
; pointers ends


Quicksort_Top proc far
; 函数：调用快速排序函数按成绩排序学生信息

    mov ax,data

    ; mov ax,0h
    ; mov bx,1h
    ; call far ptr Compare_ax_bx


    mov ax,ss:[bp+16h]  ;总人数
    cmp ax,0h
    jz Quicksort_Top_error_no_informations
    dec ax
    push ax
    lea ax,data_start
    push ax
    call far ptr Quicksort
    add sp,4h

    dispmsg Sort_information_success

    retf
Quicksort_Top_error_no_informations:
    dispmsg Sort_information_no_informations_error
    retf





Quicksort_Top endp

;================================================================

Quicksort proc far
; 函数：快速排序算法
; 参数: 存放在栈中
; sort_l = ss:[bp+6]
; sort_r = ss:[bp+8]
    push bp    
    mov bp,sp
    ; addr = ss:[bp-2]
    ; value = ss:[bp-4]
    xor ax,ax
    push ax
    push ax

    push ax
    push bx
    push cx
    push dx
    push si
    push ds


    
    mov ax,ss:[bp+6]
    cmp ax,ss:[bp+8]
    jnb  Quicksort_done       ;l>=r return
    ; l<r 继续
Quicksort_continue:

    mov dx,pointers
    mov ds,dx

    mov bx,ss:[bp+6]

    xor bx, bx      
    mov si,ss:[bp+6]    ;i=l
    mov bx,ss:[bp+8]    ;j=r
         ; l*=2 以字为单位

    ; mov ax, ds:[si]     ;用ax保存base = pointers[l]
    mov ax,si
    mov ss:[bp-2], si
    mov ss:[bp-4], ax  
    inc si               ;i+=1

    cmp si,bx 
    jnb Quicksort_find_j_above_base
    jmp Quicksort_cycle

;结束函数
Quicksort_done:
    pop ax
    mov ds,ax
    pop si
    pop dx
    pop cx
    pop bx
    pop ax
    add sp,4h
    pop bp
    retf


; 循环
Quicksort_cycle:
    cmp si,bx      ;while (i!=j)  / i<j
    jnb Quicksort_over_cycle   ; i=j  跳出循环
        
Quicksort_find_j_above_base:
    call  far ptr Compare_ax_bx
    cmp  dx,2h      ; ax < bx    x<j
    jz Quicksort_found_j
    cmp si,bx
    jnb Quicksort_over_cycle ; i>=j 跳出循环
    dec bx ; j-=1
    jmp Quicksort_find_j_above_base
Quicksort_found_j:

    push si
    push bx
    push bx

    mov ss:[bp-2], bx

    mov dx,bx
    mov si,ax
    shl si,1h
    shl bx,1h

    mov cx,ds:[si]
    mov dx,ds:[bx]
    mov ds:[bx],cx
    mov ds:[si],dx



    pop ax
    pop bx
    pop si

Quicksort_find_i_below_base:

    call far ptr Compare_ax_si
    cmp  dx,3h       ; ax > si   x>i
    jz Quicksort_found_i
    cmp si,bx 
    jnb Quicksort_over_cycle  ; i>=j 跳出循环
    inc si   ; i+=1
    jmp Quicksort_find_i_below_base


Quicksort_found_i:


    push si
    push bx
    push si

    mov ss:[bp-2], si

    mov dx,si
    mov bx,ax
    shl bx,1h
    shl si,1h

    mov cx,ds:[bx]
    mov dx,ds:[si]
    mov ds:[si],cx
    mov ds:[bx],dx



    pop ax
    pop bx
    pop si

    jmp Quicksort_cycle



Quicksort_over_cycle:

    mov ax,ss:[bp+6]
    mov cx,ss:[bp+8]
    ;

    ; mov es,si
    ; jmp Quicksort_done
    mov si,ss:[bp-2]
    ; shr si,1h


Quicksort_recursion1:
    push si                 ; si = i
    dec si                  ; i-=1

    cmp si,ss:[bp+6]
    jle Quicksort_recursion2 ; i <= left 时不进行递归

    push si                 ;push i-1
    push ss:[bp+6]          ;push l
    call Quicksort        ;quicksort(l, i-1);
    add sp,4h

Quicksort_recursion2:
    pop si                   ; 复原i
    inc si

    cmp si,ss:[bp+8]
    jnl Quicksort_done_tranfer  ; i >= right 时不进行递归

    push ss:[bp+8]          ;push r
    push si                 ;push i+1
    call Quicksort          ;quicksort(i+1, r);
    add sp,4h
Quicksort_done_tranfer:
    jmp Quicksort_done



Quicksort endp


;================================================================

Compare_ax_si proc far
; 函数：比较data[pointer[ax]]和data[pointer[si]]的大小，返回值在dx上
    push ax
    push bx
    push cx
    push si
    push ds
    push ax
    push si


    mov ax,pointers
    mov ds,ax
    pop bx
    shl bx,1h
    mov ax,ds:[bx]


    mov dx,data
    mov ds,dx
    mov si,ax
    mov cl,ds:[si+2Fh]   ;cx = data[si]
    xor ch,ch

    mov ax,pointers
    mov ds,ax
    pop bx
    shl bx,1h
    mov ax,ds:[bx]

    mov dx,data
    mov ds,dx
    mov si,ax
    mov dl,ds:[si+2Fh]   ;dx = data[ax]
    xor dh,dh

    cmp dx,cx
    ja Compare_ax_si_above
    jb Compare_ax_si_below

Compare_ax_si_equal:
    mov dx,1h
    jmp Compare_ax_si_done
Compare_ax_si_below:
    mov dx,2h
    jmp Compare_ax_si_done
Compare_ax_si_above:
    mov dx,3h

Compare_ax_si_done:
    pop ax
    mov ds,ax
    pop si
    pop cx
    pop bx
    pop ax
    retf
Compare_ax_si  endp
;=================================================
Compare_ax_bx proc far
; 函数：比较data[ax]和data[bx]的大小，返回值在dx上
    push ax
    push cx
    push bx
    push si
    push ds
    push ax
    push bx


    mov ax,pointers
    mov ds,ax
    pop bx
    shl bx,1h
    mov ax,ds:[bx]


    mov dx,data
    mov ds,dx
    mov si,ax
    mov cl,ds:[si+2Fh]   ;cx = data[bx]
    xor ch,ch

    mov ax,pointers
    mov ds,ax
    pop bx
    shl bx,1h
    mov ax,ds:[bx]

    mov dx,data
    mov ds,dx
    mov si,ax
    mov dl,ds:[si+2Fh]   ;dx = data[ax]
    xor dh,dh

    cmp dx,cx
    ja Compare_ax_bx_above
    jb Compare_ax_bx_below

Compare_ax_bx_equal:
    mov dx,1h
    jmp Compare_ax_bx_done
Compare_ax_bx_below:
    mov dx,2h
    jmp Compare_ax_bx_done
Compare_ax_bx_above:
    mov dx,3h

Compare_ax_bx_done:    
    pop ax
    mov ds,ax
    pop si
    pop bx
    pop cx
    pop ax
    retf


Compare_ax_bx endp






